package com.huangpeng.algorithm.dataStructure;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author huangpeng
 * @Title 贪心算法
 * @Package
 * @Date 2021/7/23 15:44
 * @Description 算法 / 数据结构：贪心 / 哈希表 解题思路 统计每个数出现的次数，并将次数排序。
 * 因为只有把一个数全部取走才能使这个数彻底消失，所以优先取走出现次数少的。
 * 复杂度分析 时间复杂度：O(nlogn) 对数组进行排序需要耗费 O(nlogn)O(nlogn) 的时间复杂度  空间复杂度：O(n) 哈希表和统计次数的数组耗费的空间是 O(n)O(n)
 * @Version 1.0
 */
public class Greedy {
    private List<Integer> ids = new ArrayList<Integer>();//测试数据-物品种类
    private int m = 2;//需要拿走的物品种类

    public List<Integer> getIds() {
        ids.add(1);
        ids.add(1);
        ids.add(1);
        ids.add(2);
        ids.add(2);
        ids.add(3);

        return ids;
    }

    public int minItem(List<Integer> ids,int m){
        if(ids.isEmpty()){
            return -1;
        }
        Map<Integer,Integer> numToCount = new HashMap<Integer, Integer>();
        ArrayList<Integer> count = new ArrayList<Integer>();
        ids.forEach(s -> {
            numToCount.put(s.intValue(),numToCount.getOrDefault(s.intValue(),0) + 1);
        });
        for(int key : numToCount.keySet()){
            count.add(numToCount.get(key));
        }
        Collections.sort(count,Collections.reverseOrder());
        while(count.size() != 0 && count.get(count.size() - 1) <= m){
            m -= count.get(count.size() - 1);
            count.remove(count.size() - 1);
        }

        return count.size();
    }

    public static void main(String[] args) {
        Greedy greedy = new Greedy();
        System.out.println(greedy.minItem(greedy.getIds(),greedy.m));
    }
}
